package com.fengye.algorithms.leecode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author fengye
 * @Date 2023/4/8 9:57
 **/
public class LC17LetterCombinations {

    public List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<>();
        if(digits == null || digits.length() == 0 || digits.equals("") || digits.equals(" ") ) {
            return list;
        }

        backtrack(list, digits, 0, new StringBuilder());
        return list;
    }

    public void backtrack(List<String> list, String digits, int index, StringBuilder sb) {
        if(index == digits.length()) {
            list.add(sb.toString());
            return;
        }

        String letters = map(digits.charAt(index));
        for(int i=0;i<letters.length();i++) {
            // 选
            sb.append(letters.charAt(i));
            backtrack(list, digits, index+1, sb);
            // 不选
            sb.deleteCharAt(index);
        }
    }

    public List<String> letterCombinations1(String digits) {
        List<String> list = new ArrayList<>();
        if(digits == null || digits.length() == 0 || digits.equals("") || digits.equals(" ") ) {
            return list;
        }

        char[] chars = digits.toCharArray();
        for (int i = 0; i <chars.length; i++) {
            list.add(map(chars[i]));
        }
        List<String> ls = new ArrayList<>();
        for(int n = 0; n < list.size(); n++) {
            String s = list.get(n);
            //把上一次结果保存
            List<String> t = new ArrayList<>(ls);
            // 处理本次结果
            ls = new ArrayList<>();
            for(int i = 0; i < s.length();i++) {
                if(n == 0) {
                    ls.add(s.charAt(i) + "");
                } else {
                    for (int j = 0; j <t.size(); j++) {
                        String ts = t.get(j) + s.charAt(i);
                        ls.add(ts);
                    }
                }
            }
        }

        return ls;
    }

    public static String map(char c) {
        switch(c) {
            case '2' : return "abc";
            case '3' : return "def";
            case '4' : return "ghi";
            case '5' : return "jkl";
            case '6' : return "mno";
            case '7' : return "pqrs";
            case '8' : return "tuv";
            case '9' : return "wxyz";
            default: return "";
        }
    }
}
